This invention relates to computer multiplication in general and more particularly to an efficient combined multiplier array which can carry out multiplications on different length operands.
Various types of multipliers for use in computers have been developed. One of these types, known as a combinational array multiplier, utilizes an array including a plurality of carry save adders feeding a carry propagate adder from which the result is obtained. Such combined arrays in many instances have relied upon Booth's algorithm. See for example, Computer Architecture and Organization, 2nd Ed. by John P. Hayes, McGraw Hill, 1988, particularly pages 241-250. A detailed implementation of Booth's algorithm is described in U.K. Patent Application GB 2,262,638A, published Jun. 23, 1993, particularly in FIGS. 9-12.
The general arrangement of a specific combinational multiplier that can perform four 16.times.16 multiplications is illustrated in FIG. 1. The arrangement shown includes a first register 10 containing a first operand X comprising 64 bits and a second register 20 containing operand Y comprising 64 bits. One skilled in the art will appreciate that registers 10 and 20 can be any of a variety of other storage devices such as accumulators. Four groups of 16 of the 64 bits in register 10 provide the A, C, E, and G inputs for four 16.times.16 multipliers 15 a-d. Similarly, 16 bit groups of the register 20 (i.e., B, D, F, and H) are provided as inputs to four Booth encoders 19, and the outputs of the Booth encoders 19 are coupled as inputs to multipliers 15 a-d. Each of the multipliers generates a 32-bit output. These 32-bit outputs are used to generate the result of the multiplication of operands X and Y. As is known in the art, output shift and multiplexers (not shown specifically in FIG. 1) can be used to select the appropriate multiplier outputs for the result.
The same techniques can, of course, be utilized for multiplying larger or smaller numbers of bits. In current computers, at least 16 bit multiplications are required. In some instances, however, being able to multiply smaller numbers of bits has advantages. For example, the ability to do two 8 bit multiplications instead of a single 16 bit multiply can give significant performance advantages for low end graphics and video game applications. It can also provide a speed up for certain signal processing routines. Although it would be possible to implement 8 bit multiplies with separate 8 bit multiplier arrays, these arrays are an expensive resource. Thus, there is a need to provide an efficient combined array which can carry out both 2 n bit and n bit multiplications, e.g., where n=8. Stated another way, there is a need to have, in a processor which includes a multiplier array which can multiply a pair of 2 n bit numbers, the capability, using the same array, to also multiply two pairs of n bit numbers simultaneously.